package offer.offer03;

import java.util.*;

/**
 * binarySearch的一个实践,
 *
 */
public class S49丑数 {
    public static void main(String[] args) {
        S49丑数.nthUglyNumber(1690);
    }

    /**
     * 5。把开局的LinkedList换成ArrayList之后终于能用了, 提升5倍 但是还是很慢, O(nlogn)的复杂度看来仍旧无法接受。
     * 一个有序的List, 我们不断从前往后找到数, 把它*2, *3, *5 的结果添加进去
     * 注意: 不能在添加的时候计数, 因为记到n个数的时候, 前面n个数之间还有很多丑数没有添加。
     * 此方法也没有剪枝, 比如12 会是 1*2*2*3, 也是1*2*3*2等, 会被多次计数, n越大这个数值的损失越大。
     *
     * 不能用array, 因为你在插入的时候, 其实是不知道他的大小顺序的, 后面来的值有的会插到前面之前, 所以要binarySearch。
     */
    public static int nthUglyNumber(int n) {
        List<Integer> totoalList = new ArrayList<>(); // 本来是LinkedList, 看来还是要注意。
        totoalList.add(1);
        int totalCount = 0;
        int limit = Math.min(n*3, 1690);
        // 用了一堆变量, 试图减小一下计算开销, 但是因为重复计算, 还是很耗时。
        int curAdd;
        int curPosi;
        for(int i = 0; totalCount < limit; i++){
            Integer curNum = totoalList.get(i);
            curAdd = curNum * 2; // 这个数是会超过max_value的, 然后会变成负的, 插入会破坏序列。
            curPosi = Collections.binarySearch(totoalList, curAdd);
            if(curPosi < 0 && curAdd > 0 && totalCount ++ >= 0)
                totoalList.add(- curPosi - 1, curAdd);
            curAdd = curNum * 3;
            curPosi = Collections.binarySearch(totoalList, curAdd);
            if(curPosi < 0 && curAdd > 0 && totalCount ++ >= 0)
                totoalList.add(- curPosi - 1, curAdd);
            curAdd = curNum * 5;
            curPosi = Collections.binarySearch(totoalList, curAdd);
            if(curPosi < 0 && curAdd > 0 && totalCount ++ >= 0)
                totoalList.add(- curPosi - 1, curAdd);
        }
        return totoalList.get(n - 1);
    }

    /**
     * 动态规划
     * 别人的, 三个指针分别指向 *2, *3, *5 的三个位置,
     * 一些动态规划为什么不会错过一些值我总是搞不明白
     */
    public int nthUglyNumber2(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}
